|
|
Unendliche Graphentheorie, WS 2023/24
Vorlesungstermine
Montags, 12:15 - 13:45 Uhr, Geomatikum H5
Mittwochs, 10:15 - 11:45 Uhr, Geomatikum H5
Übungstermine
Montags, 14:15 - 15:45 Uhr, Sedanstr 19, Raum 203 (Thilo Krill)
|
Inhalt
Die Graphentheorie ist eines der
jüngsten und zugänglichsten Gebiete der Mathematik.
Hier begegnet man vom ersten Tag an
mathematischen Problemen, die man im Prinzip ohne
weitere Voraussetzungen selbst bearbeiten könnte. Unendliche Graphentheorie ist ein faszinierendes Teilgebiet der Graphentheorie, deren Reiz unter anderem darin besteht, dass Beweise im Gegensatz zu den endlichen Induktionsbeweisen viel algorithmischer und konstruktiver sein müssen -- und dann oftmals auch neue Einblicke im Rückschluss auf endliche Graphen erlauben.
Voraussetzungen
Die Vorlesung wendet sich typischerweise an Hörer im
Mastersemester, und setzt das Material aus der Graphentheorie 1 voraus. Vorherige oder gleichzeitige Teilnahme an der Vorlesung
"Graphentheorie 2" ist nicht Voraussetzung. Bekanntschaft mit etwas Logik und Mengenlehre (Ordinalzahlen etc) ist vorteilhaft aber nicht nötig.
Übungsblätter
Zur Vorlesung gibt es Übungen, die durchaus
über den Vorlesungsstoff hinausgehen können und auf die aktuelle Forschung hinführen. Die Übungsblätter erscheinen im wöchentlichen Rhythmus. Ausgewählte Aufgaben sind schriftlich zu bearbeiten und abzugeben. Ihre Lösungen zu den restlichen Aufgaben werden Sie in den Übungen mündlich präsentieren. Hierzu tragen Sie sich jeweils vor der Übung in eine Liste ein, welche Aufgaben Sie gelöst haben und bereit sind, vorzutragen. Denken Sie beim Vortragen an das Schema: Situation -- Complication -- Solution, d.h. erinnern Sie Ihre Kommilitonen kurz daran, was eigentlich das Problem / die Aufgabe war, wo eventuell die Schwierigkeit der Aufgabe liegt, und erst dann, wie Ihre Lösung aussieht.
Leistungsnachweis
Bestehen der schriftlichen/mündlichen Prüfung. Für die Prüfungszulassung wird eine erfolgreiche Teilnahme an der Übung vorausgesetzt (Lösen von mindestens 50% der Aufgaben). Wenn Sie eine Woche wegen Krankheit verpassen, wird diese Woche bei Vorlegen eines Attests (kurze Email an mich) von den 50% rausgerechnet.) Allgemeine Tipps zum Ablauf,
zur Vorbereitung, und zum Prüfungsstoff gibt es hier.
Material
- R. Diestel, Graph Theory (5th ed'n), GTM 173, Springer 2017. Online verfügbar aus dem Uni-Netzwerk. Achtung: Die deutsche Version des Buches enthält das Kapitel über unendliche Graphen n i c h t.
- Deutsch-englisches Glossar.
- A. Soifer, The Mathematical Colouring Book Springer 2009. Online verfügbar aus dem Uni-Netzwerk.
- P. Komjath, Erdös's Work on Infinite Graphs Springer 2013. Online verfügbar aus dem Uni-Netzwerk.
- There is also a typed script for this lecture. Email me if you are interested in a copy.
Logbuch
- 16. Oktober: First examples of infinite graphs. Unit distance graphs. Nelson Hadwiger Problem. The rational plane is bipartite. (Normal) spanning trees in countable graphs.
- 18. Oktober: The infinite Ramsey theorem. König's Infinity lemma. The de Bruijn-Erdös theorem for countable graphs. The finite Ramsey theorem. The Schröder-Cantor-Bernstein Theorem. Menger's Theorem for infinite graphs.
- 23. Oktober: Ordered Sets and Zorn's lemma. The spanning tree theorem and the de Bruijn-Erdös theorem for arbitrary graphs from Zorn's lemma.
- 25. Oktober: Well-orders and the Well-Ordering Principle. The spanning tree theorem and the de Bruijn-Erdös theorem for arbitrary graphs from the Well-Ordering Principle.
- 30. Oktober: Ordinal numbers and the equivalence of Choice, Zorn's lemma, the Well-ordering principle, and the spanning tree theorem.
- 1. November: Ultrafilters and the Ultrafilter lemma. The de Bruijn-Erdös theorem for arbitrary graphs from the ultrafilter lemma, and from the Generalized infinity lemma. Proof of the Generalized infinity lemma via ultrafilters.
- 6. November: Initial ordinals and cardinals. Cardinal arithmetic. Mazurkiewicz theorem on the existence of a 2-point set in the plane.
- 8. November: Regular and singular cardinals. The Dushnik-Erdös-Miller theorem. Rays in infinite graphs. Halin's theorem on the existence of linked ray decompositions with disjoint separators of locally finite graphs.
- 13. November: Halin's theorem on the supremum of the number of A-rays. The ubiquity conjecture. Ubiquity of the ray. Definitions around ends: End, degree, dominating vertices. Degree witnessing pairs for undominated ends.
- 15. November: Degree witnessing sequences for undominated ends. The supremum in the definition of the end degree is a maximum. Halin's Menger type theorem for vertices and ends. Directions. The Diestel-Kühn-Direction Theorem.
- 20. November: Ray graphs for ends of finite degree. Ray graphs for ends of countably infinite degree: Halin's grid theorem. Connectivity in infinite graphs. The pressing down lemma. Halin's theorem that every k-connected graph of uncountable regular size kappa contains a subdivided K(k,kappa).
- 22. November: Star-Comb Lemma. Second proof of Halin's theorem that every k-connected graph of uncountable regular size kappa contains a subdivided K(k,kappa). The Oporowski-Oxley-Thomas Theorem on typical subgraphs of k-connected, countably infinite graphs. Characterisations of infinitely connected graphs (Dirac-Thomassen).
- 27. November: A sufficient condition for subdivided K(kappa). Closure and reflection arguments. The rational distance graph has countable chromatic number (Erdös-Hajnal).
- 29. November: The colouring number. The Erdös-Hajnal Theorem that every graph with uncountable colouring number contains a K(n,aleph_1) for all integers n, as well as the infinite half graph H_{omega,omega+1}. Every graph with uncountable chromatic number contains cycles of all sufficiently large lengths (Hajnal-Komjath-Shelah, Thomassen).
- 4. December: Directed line graphs and the shift graph. Existence of graphs with large chromatic number and large odd girth (Erdös-Hajnal). Equivalence of containing K_kappa minors and K(kappa) subdivision. Halin's answer to the infinite Hadwiger conjecture.
- 6. December: Order trees, generalized paths (Rado), T-graphs (Brochet-Diestel). Existence of TK(kappa) in T-graphs. Halin's example that his infinite Hadwiger theorem is sharp.
- 11. December: Normal trees and normal spanning trees. Dispersed sets. Jung's characterisations of normally spanned sets of vertices.
- 13. December: Halin's and Diestel's NST criterions. Weakly dispersed sets. A graph has an NST iff it is a countable union of sets each of which can be separated from every fat TK(aleph0) by a finite set of vertices. Diestel's theorem characterizing the TK(aleph0)-free graphs. (Chapter 6, except 6.3).
- 18. December: Robertson-Seymour Thomas Theorem 7.1.1: Kappa-directions are induced by K(kappa) minors. Ranking of rayless graphs. Kappa-rank. Kappa-escapes. Rayless tree-decompositions of graphs with kappa-rank (Theorem 2.5.3).
- 20. December: Seymour Thomas Theorem 7.2.5: A graph has a kappa-rank iff it contains no T_kappa minor. The existence of narrow normal partition trees (Brochet-Diestel).
- 8. Januar: The Robertson-Seymour-Thomas structure theorem for graphs without K(kappa) subdivisions.
- 10. Januar: End-faithful spanning tree counterexamples (Komjath, Seymour-Thomas, Thomassen). Every graph without subdivided T(aleph_1) has an end-faithful spanning tree (Polat).
- 15. Januar: Rayless spanning trees and dominating vertices (Polat-Siran). The envelope lemma (Kurkofka-Pitz). Every connected graph has a spanning tree that is end-faithful for its undominated ends (Carmesin).
- 17. Januar: Ubiquity of the ray -- another proof via the linking lemma.
- 22. Januar: The concentration lemma. Topological ubiquity of subtrees of the binary tree (Halin). The pebble pushing game. Minor ubiquity of the full grid.
- 24. Januar: Nash-Williams's cycle decomposition theorem and Laviolette's cut-faithful decomposition theorem.
|
